package Hot100.Easy.LC448;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

public class LC448 {
    public static void main(String[] args) {
        int[] nums = {4, 3, 2, 7, 8, 2, 3, 1};
        LC448 solution =  new LC448();
        System.out.println(solution.findDisappearedNumbers(nums));
    }

    public List<Integer> findDisappearedNumbers(int[] nums){
//      ArrayList<Integer> res = new ArrayList<>();

        int n = nums.length;
        HashSet<Integer> res = new HashSet<>();// 使用Set时，后面remove删除元素时时间复杂度为O（1）
        for(int i = 1; i <= n; i++){
            res.add(i);
        }

        for(int i = 0; i < n; i++){
            if(res.contains(nums[i])){
                res.remove(Integer.valueOf(nums[i]));
            }
        }
        return new ArrayList<>(res);
    }
}
